#include <iostream>
#include <cstdlib>
#include <list>
#include <vector>
#include <string>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define INFINITY 2147483647
#define MAX_VERTEX_NUM 20

using std::vector;

typedef int Status;
typedef int VRType;
typedef char InfoType;
typedef enum{DG, DN, UDG, UDN} GraphKind;
typedef int VertexType;
typedef struct ArcCell
{
	VRType adj;
	InfoType *info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

class MGraph
{
private:
	VertexType vexs[MAX_VERTEX_NUM];
	bool visited[MAX_VERTEX_NUM];
	AdjMatrix arcs;
	int vexnum, arcnum;
	GraphKind Graphkind;
public:
	MGraph(GraphKind gk);
	Status CreateGraph();
	Status DestroyGraph();
	int LocateVex(VertexType u);
	Status GetVex(VertexType v);
	Status PutVex(VertexType v, VertexType value);
	VertexType FirstAdjVex(VertexType v);
	VertexType NextAdjVex(VertexType v, VertexType w);
	Status InsertVex(VertexType v);
	Status DeleteVex(VertexType v);
	Status InsertArc(VertexType v, VertexType w, int weight);
	Status DeleteArc(VertexType v, VertexType w);
	Status DFSTraverse(Status (*visit)(VertexType v), int v, int f);
	Status BFSTraverse(Status (*visit)(VertexType v), int startVex);
	friend Status topoSort(MGraph G, vector<int> &result);
	friend vector<int> getKeyPath(MGraph net, vector<int> topoArr);
};
